2017 Kakao Advanced to a final

Group Photo (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/1835
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
struct _d{
int a, b, cnt, code;
};
int abs_v(int a){
return a<0?-a: a;
}
int solution(int n, vector<string> data){
char friends[]="ACFJMNRT";
int answer=0;
int a, b, code, cnt=0, i, pos[8], can, d;
map<char, int> comp;
vector<_d> pool;
vector<int> p;
for(i=0; i<8; ++i){
comp.insert({friends[i], i});
p.push_back(i);
}
for(string& s: data){
a=comp[s[0]], b=comp[s[2]];
cnt=s[4]-'0', code=s[3];
pool.push_back(_d{a, b, cnt, code});
}
do{
for(i=0; i<8; ++i) pos[p[i]]=i;
can=1;
for(_d& e: pool){
d=abs_v(pos[e.a]-pos[e.b])-1;
switch(e.code){
case '>': can&=(d>e.cnt); break;
case '<': can&=(d<e.cnt); break;
case '=': can&=(d==e.cnt); break;
}
}
answer+=can;
}while(next_permutation(p.begin(), p.end()));
return answer;
}
int main(void){
int n=2;
vector<string> data={
"N~F=0", "R~T>2"
};
int result=solution(n, data);
std::cout<<"result: "<<result<<std::endl;
return 0;
}
Sichuan Game (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/1836
#include <iostream>
#include <vector>
#include <map>
#include <cctype>
#include <cassert>
using namespace std;
int find_route(vector<vector<int>> board, vector<int> ord){
int can, xmin, xmax, ymin, ymax, value;
for(int i=0; i<ord.size(); ++i){
vector<vector<int>> position;
for(int j=0; j<board.size(); ++j){
for(int k=0; k<board[0].size(); ++k){
if(board[j][k]==ord[i]) position.push_back({j, k});
}
}
assert(position.size()==2);
ymin=min(position[0][0], position[1][0]); ymax=max(position[0][0], position[1][0]);
xmin=min(position[0][1], position[1][1]); xmax=max(position[0][1], position[1][1]);
value=ord[i];
can=1;
for(int j=ymin; j<=ymax; ++j){
if(board[j][xmin]!=0 && board[j][xmin]!=value){
can=0;
break;
}
}
if(can){
for(int j=xmin; j<=xmax; ++j){
if(board[ymax][j]!=0 && board[ymax][j]!=value){
can=0;
break;
}
}
}
if(can){
board[position[0][0]][position[0][1]]=0;
board[position[1][0]][position[1][1]]=0;
continue;
}
can=1;
for(int j=xmin; j<=xmax; ++j){
if(board[ymin][j]!=0 && board[ymin][j]!=value){
can=0;
break;
}
}
if(can){
for(int j=ymin; j<=ymax; ++j){
if(board[j][xmax]!=0 && board[j][xmax]!=value){
can=0;
break;
}
}
}
if(can){
board[position[0][0]][position[0][1]]=0;
board[position[1][0]][position[1][1]]=0;
continue;
} else {
return 0;
}
}
return 1;
}
string solution(int m, int n, vector<string> board){
string answer="";
vector<vector<int>> num_board(m, vector<int>(n));
map<char, int> comp;
vector<int> p;
int count=1, state;
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
if (!isalpha(board[i][j])) continue;
if(comp.find(board[i][j])==comp.end()){
comp.insert({board[i][j], count});
count++;
}
}
}
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
num_board[i][j]=board[i][j]=='*'? -1: board[i][j]=='.'? 0: comp[board[i][j]];
}
}
for(auto iter=comp.begin(); iter!=comp.end(); ++iter){
p.push_back(iter->second);
}
state=0;
sort(p.begin(), p.end());
do{
if(find_route(num_board, p)){
state=1;
break;
}
}while(next_permutation(p.begin(), p.end()));
//
if(state){
for(int i=0; i<p.size(); ++i){
for(auto iter=comp.begin(); iter!=comp.end(); ++iter){
if(iter->second==p[i]) answer+=iter->first;
}
}
} else {
answer="IMPOSSIBLE";
}
return answer;
}
int main(void){
int m, n;
vector<string> board1={
"DBA", "C*A", "CDB."
};
vector<string> board2={
"NRYN", "ARYA"
};
vector<string> board3={
".ZI.", "M.**", "MZU.", ".IU."
};
vector<string> board4={
"AB", "BA"
};
string answer1=solution(board1.size(), board1[0].size(), board1);
string answer2=solution(board2.size(), board2[0].size(), board2);
string answer3=solution(board3.size(), board3[0].size(), board3);
string answer4=solution(board4.size(), board4[0].size(), board4);
std::cout<<"answer1: "<<answer1<<std::endl;
std::cout<<"answer2: "<<answer2<<std::endl;
std::cout<<"answer3: "<<answer3<<std::endl;
std::cout<<"answer4: "<<answer4<<std::endl;
return 0;
}
GPS (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/1837
#include <iostream>
#include <vector>
using namespace std;
void find_route(vector<vector<int>> edge_list, vector<int> gps, vector<int> route, int& mini_num){
if (route.size()==gps.size()){
if(gps[gps.size()-1]==route[route.size()-1]){
int count=0;
for(int i=1; i<gps.size(); ++i){
if(gps[i]!=route[i]) count++;
}
if(mini_num>count){
mini_num=count;
return;
} else return;
} else {
return;
}
}
int current=route[route.size()-1];
vector<int> can_go;
for(int i=0; i<edge_list.size(); ++i){
if(edge_list[i][0]==current) can_go.push_back(edge_list[i][1]);
if(edge_list[i][1]==current) can_go.push_back(edge_list[i][0]);
}
for(int go: can_go){
vector<int> tmp(route.size());
std::copy(route.begin(), route.end(), tmp.begin());
tmp.push_back(go);
if(tmp.size()>gps.size()) return;
find_route(edge_list, gps, tmp, mini_num);
}
}
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log){
int answer=k, point, state=1;
vector<int> route;
for(int i=0; i<k-1; ++i){
vector<int> prev_now={gps_log[i], gps_log[i+1]};
sort(prev_now.begin(), prev_now.end());
if(edge_list.end()==find(edge_list.begin(), edge_list.end(), prev_now)){
// MISS
state=0;
}
}
if(state) return 0;
route.push_back(gps_log[0]);
find_route(edge_list, gps_log, route, answer);
return answer;
}
int main(void){
int n=7, m=10, k=6;
int answer1, answer2;
vector<vector<int>> edge_list={
{1, 2},
{1, 3},
{2, 3},
{2, 4},
{3, 4},
{3, 5},
{4, 6},
{5, 6},
{5, 7},
{6, 7}
};
vector<int> gps_log1={1, 2, 3, 3, 6, 7};
vector<int> gps_log2={1, 2, 4, 6, 5, 7};
answer1=solution(n, m, edge_list, k, gps_log1);
answer2=solution(n, m, edge_list, k, gps_log2);
std::cout<<"answer1: "<<answer1<<std::endl;
std::cout<<"answer2: "<<answer2<<std::endl;
return 0;
}
Consider of Trainer Lion (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/1838
#include <iostream>
#include <vector>
using namespace std;
int t_dup(vector<int> time1, vector<int> time2){
vector<int>* first;
vector<int>* second;
if(time1[0]<time2[0]) {
first=&time1;
second=&time2;
}
else {
first=&time2;
second=&time1;
};
if(first->at(1)>=second->at(0)) return 1;
else return 0;
}
int tt_dup(vector<vector<int>> timetable){
int mi=1320, ma=600;
for(int i=0; i<timetable.size(); ++i){
if(timetable[i][0]<mi) mi=timetable[i][0];
if(timetable[i][1]>ma) ma=timetable[i][1];
}
int dup_max=0;
int tmp;
for(int crt=mi; crt<=ma; ++crt){
tmp=0;
for(int i=0; i<timetable.size(); ++i){
if(crt>=timetable[i][0] && crt<=timetable[i][1]) tmp++;
}
if(dup_max<tmp) dup_max=tmp;
}
return dup_max;
}
int min_far(int n, int num){
int surface=(n-1)*4;
return surface/num;
}
int solution(int n, int m, vector<vector<int>> timetable){
int answer=0;
if(m==1) return 0;
int state=0, count=0;
vector<vector<int>> inter;
for(int i=0; i<timetable.size(); ++i){
for(int j=i+1; j<timetable.size(); ++j){
state=t_dup(timetable[i], timetable[j]);
if(state==1) {
inter.push_back(vector<int>{i, j});
count+=state;
}
}
}
if(count==1) return 2*(n-1);
count=tt_dup(timetable);
answer=min_far(n, count);
return answer;
}
int main(void){
typedef vector<vector<int>> vector2;
int answer1, answer2, answer3, answer4;
vector2 timetable1={
{1170, 1210},
{1200, 1260}
};
vector2 timetable2={
{840, 900}
};
vector2 timetable3={
{600, 630},
{630, 700}
};
vector2 timetable4={
{1140, 1200},
{1150, 1200},
{1100, 1200},
{1210, 1300},
{1220, 1280}
};
answer1=solution(3, timetable1.size(), timetable1);
answer2=solution(2, timetable2.size(), timetable2);
answer3=solution(2, timetable3.size(), timetable3);
answer4=solution(4, timetable4.size(), timetable4);
std::cout<<"answer1: "<<answer1<<std::endl;
std::cout<<"answer2: "<<answer2<<std::endl;
std::cout<<"answer3: "<<answer3<<std::endl;
std::cout<<"answer4: "<<answer4<<std::endl;
return 0;
}
Tube’s blind date (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/1839
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void find_route(vector<vector<int>> time_map, vector<int> loc, int t, const int& s, int rou, vector<int>& ans){
if(loc[0]>time_map.size()-1 || loc[0]<0 || loc[1]<0 || loc[1]>time_map[0].size()-1) return;
if(time_map[loc[0]][loc[1]]==-1) return;
if(loc[0]==time_map.size()-1 && loc[1]==time_map[0].size()-1){
if(ans[1]>t){
ans[0]=rou;
ans[1]=t;
}
}
t+=time_map[loc[0]][loc[1]];
if(t>s) return;
rou++;
time_map[loc[0]][loc[1]]=-1;
vector<int> tmp(2);
copy(loc.begin(), loc.end(), tmp.begin()); tmp[0]--;
find_route(time_map, tmp, t, s, rou, ans);
copy(loc.begin(), loc.end(), tmp.begin()); tmp[0]++;
find_route(time_map, tmp, t, s, rou, ans);
copy(loc.begin(), loc.end(), tmp.begin()); tmp[1]--;
find_route(time_map, tmp, t, s, rou, ans);
copy(loc.begin(), loc.end(), tmp.begin()); tmp[1]++;
find_route(time_map, tmp, t, s, rou, ans);
}
vector<int> solution(int m, int n, int s, vector<vector<int>> time_map){
vector<int> loc={0, 0};
vector<int> answer(2);
for(int i=0; i<time_map.size(); ++i){
for(int j=0; j<time_map[0].size(); ++j){
answer[1]+=time_map[i][j];
}
}
answer[0]=0;
find_route(time_map, loc, 0, s, 0, answer);
return answer;
}
void print(vector<int> answer){
std::cout<<"["<<answer[0]<<", "<<answer[1]<<"]"<<std::endl;
}
int main(void){
typedef vector<vector<int>> vector2;
int s1=150, s2=25, s3=12;
vector2 time_map1={
{0, 2, 99},
{100, 100, 4},
{1, 2, 0}
};
vector2 time_map2={
{0, 1, 1, -1, 2, 4},
{-1, 7, 2, 1, 5, 7},
{-1, 1, -1, 1, 6, 3},
{-1, 1, -1, -1, 7, 0}
};
vector2 time_map3={
{0, 1, 1, 1, 1},
{9, 9, 9, 1, 9},
{1, 1, 1, 1, 9},
{1, 1, 5, 9, 9},
{1, 1, 1, 1, 0}
};
vector<int> answer1, answer2, answer3;
answer1=solution(time_map1.size(), time_map1[0].size(), s1, time_map1);
answer2=solution(time_map2.size(), time_map2[0].size(), s2, time_map2);
answer3=solution(time_map3.size(), time_map3[0].size(), s3, time_map3);
print(answer1); print(answer2); print(answer3);
return 0;
}
Neo’s Earring (Lv. 5)
https://school.programmers.co.kr/learn/courses/30/lessons/1842
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
int btf_sqr(vector<int> b1, vector<int> b2){
if(b2[0]>=b1[0] || b1[1]>=b2[1]) return 0;
int kk=b1[0]-b2[0]+b2[1]-b1[1];
if(kk!=b1[2]) return 0;
return 1;
}
void count(const vector<vector<int>>& point, vector<int> choose, int& answer){
typedef unsigned int uint;
const uint crt=1'000'000'007;
int state=0;
if(choose.size()>point.size()) return;
if(choose.size()>1){
int b1=choose[choose.size()-1], b2=choose[choose.size()-2];
if(!btf_sqr(point[b1], point[b2])) return;
}
if(choose[choose.size()-1]==point.size()-1){
answer++;
return;
}
for(int i=1; i<point.size(); ++i){
state=0;
for(int ch: choose) if(ch==i) state=1;
if(state) continue;
choose.push_back(i);
count(point, choose, answer);
choose.pop_back();
answer%=crt;
}
}
vector<int> solution(int n, vector<vector<int>> point, vector<vector<int>> query){
vector<int> answer;
int counter=0;
vector<int> choose={0};
vector<vector<int>> point_t={point.size(), vector<int>(point[0].size())};
copy(point.begin(), point.end(), point_t.begin());
count(point_t, choose, counter);
answer.push_back(counter);
for(int i=0; i<query.size(); ++i){
copy(point.begin(), point.end(), point_t.begin());
choose={0};
counter=0;
if(query[i][0]==0){
vector<int> tmp={query[i][1], query[i][2], query[i][3]};
point_t.insert(point_t.end()-1, tmp);
} else {
for(int j=0; j<point_t.size(); ++j){
if(point_t[j][0]==query[i][1] && point_t[j][1]==query[i][2]){
point_t.erase(point_t.begin()+j);
}
}
}
count(point_t, choose, counter);
answer.push_back(counter);
}
return answer;
}
int main(void){
typedef vector<vector<int>> vector2;
vector2 point={
{0, 4, 1},
{2, 2, 4},
{4, 0, 4}
};
vector2 query={
{0, 3, 3, 4},
{0, 3, 1, 2},
{1, 2, 2, 0}
};
assert(point.size()==query.size());
vector<int> answer=solution(point.size(), point, query);
assert(answer.size()==query.size()+1);
cout<<"[";
for(int i=0; i<answer.size()-1; ++i) cout<<answer[i]<<", ";
cout<<answer[answer.size()-1]<<"]"<<endl;
return 0;
}
Smart Prodo (Lv. 5)
https://school.programmers.co.kr/learn/courses/30/lessons/1840
Not Solved yet
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
typedef vector<int> vector1;
typedef vector<vector<int>> vector2;
int check(vector1 a, vector1 b, vector1 e){
vector1 point;
for(int ee: e){
if(find(point.begin(), point.end(), a[ee-1])==point.end()){
point.push_back(a[ee-1]);
} else return 0;
if(find(point.begin(), point.end(), b[ee-1])==point.end()){
point.push_back(b[ee-1]);
} else return 0;
}
return 1;
}
void find(const vector1& a, const vector1& b, const int& k, vector1 e, const vector1& end, vector2& process, vector2& answer, int& crt){
for(int ee: e) std::cout<<ee<<" ";
cout<<endl;
if(crt) return;
if(e.size()<k-2) return;
if(!check(a, b, e)){
process.pop_back();
return;
}
cout<<"Check1"<<endl;
if(end.size()==e.size()){
int state=0;
for(int i=0; i<e.size(); ++i){
if(e[i]!=end[i]) state=1;
}
if(!state){
answer.assign(process.size(), vector1(process[0].size()));
copy(process.begin(), process.end(), answer.begin());
crt=1;
}
}
int ll_size=e.size();
for(int i=0; i<ll_size ; ++i){
if(!(find(e.begin(), e.end(), i+1)==e.end())) continue;
for(int j=0; j<e.size(); ++j){
vector1 e_tmp(e.size());
copy(e.begin(), e.end(), e_tmp.begin());
e_tmp.erase(e_tmp.begin()+j);
vector1 pusher={0, j+1};
process.push_back(pusher);
find(a, b, k, e_tmp, end, process, answer, crt);
}
cout<<"check2"<<endl;
vector1 e_tmp(e.size());
copy(e.begin(), e.end(), e_tmp.begin());
e_tmp.push_back(i+1);
vector1 pusher={1, i+1};
process.push_back(pusher);
find(a, b, k, e_tmp, end, process, answer, crt);
}
}
vector2 solution(int n, int m, vector1 a, vector1 b, int k, int m1, int m2, vector1 e1, vector1 e2){
vector2 answer, process;
int crt=0;
find(a, b, k, e1, e2, process, answer, crt);
return answer;
}
int main(void){
int n=5, m=6, k=2, m1=2, m2=2;
vector1 a={1, 1, 2, 2, 3, 4};
vector1 b={2, 3, 3, 4, 5, 5};
assert(a.size()==b.size() && a.size()==m);
vector1 e1={3, 6}, e2={2, 4};
assert(e1.size()==m1 && e2.size()==m2);
vector2 answer=solution(n, m, a, b, k, m1, m2, e1, e2);
if(answer.size()!=0){
cout<<"[";
for(int i=0; i<answer.size()-1; ++i){
cout<<"["<<answer[i][0]<<", "<<answer[i][1]<<"], ";
}
cout<<"["<<answer[answer.size()-1][0]<<", "<<answer[answer.size()-1][1]<<"]]"<<endl;
}
return 0;
}
Conn’s Boardgame with IU
https://school.programmers.co.kr/learn/courses/30/lessons/1841